package 排序算法;
/*
* 选择排序
* 原理:
* 经过一次循环将最小的值放在最前面
* */
public class Select {
    static int[] arr1 = {3,5,1,-2,9,8};
    static int[] arr2 = {3,5,1,-2,9,8};
    static int[] arr3 = {-2,1,3,5,8,9};
    static long end;
    static long begin;
    public static void main(String[] args) {
        // 基础版
        begin = System.currentTimeMillis();
        SelectSort1(arr1);
        print(arr1);
        end = System.currentTimeMillis();
        System.out.println(end - begin);

        // 进阶版
        begin = System.currentTimeMillis();
        SelectSort2(arr2);
        print(arr2);
        end = System.currentTimeMillis();
        System.out.println(end - begin);
    }
    /*
    * 基础版
    * arr: 需要排序的数组
    * */
    public static void SelectSort1(int[] arr){
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i+1; j < arr.length; j++) {
                if(arr[i] > arr[j]){
                    int tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
    }

    /**
     * 进阶版
     * @param arr 需要排序的数组
     */
    public static void SelectSort2(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            int min = arr[i];// 记录最小值
            int minIndex = i;// 记录最小值的索引

            for (int j = i+1; j < arr.length; j++) {
                // 从索引i+1位置开始遍历,找最小值
                if(arr[j] < min){
                    min = arr[j];
                    minIndex = j;
                }
            }

            // 交换
            arr[minIndex] = arr[i];
            arr[i] = min;
        }

    }


    public static void print(int[] arr){
        for (int j : arr) {
            System.out.print(j + " ");
        }
        System.out.println();
    }
}
